import javax.swing.tree.TreeNode;

public class binarySearchTree {

    static class TreeNode {
       public int val;
       public TreeNode left;
       public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    /**
     * 搜索
     * @param val
     * @return
     */
    public boolean search(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val == val) {
                return true;
            } else if (cur.val < val) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return false;
    }
    /**
     * 插入，不可以有相同的元素，插入的位置一定是叶子结点
     * @param val
     */
    public void insert(int val) {
        //1.一个结点都没有的时候
        if(root == null) {
            root = new TreeNode(val);
            return;
        }
        //2.走到叶子结点
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else {
                return;//不可以插入相同的元素
            }
        }
        //3.判断插入叶子节点左边还是右边
        TreeNode node = new TreeNode(val);
        if(parent.val > val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
    }
    /**
     * 删除节点
     */
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                removeNode(cur,parent);
                return;
            }

        }



    }
    private void removeNode(TreeNode cur,TreeNode parent) {

        if(cur.left == null) {
            if(cur ==root) {
                root = cur.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }

        }else {//找右树最小值和cur交换
            TreeNode tmp = cur.right;//找右树的最小值
            TreeNode tmpParent = cur;//记录tmp的位置或者父亲结点
            while(tmp.left != null) {
                tmp = tmp.left;
                tmpParent = tmp;
            }
            //交换
            cur.val = tmp.val;
            if(tmpParent.right == tmp) {
                parent.right = tmp.right;
            }else {
                parent.left = tmp.right;
            }

        }
    }

}
